package com.aug_leo.datastructure.linkedlist;

/**
 * 有序链表去重
 */
public class E05Leetcode82 {


    /*
        deleteDuplicates(ListNode pointer = 1) {
            deleteDuplicates(ListNode pointer = 1) {
                deleteDuplicates(ListNode pointer = 1) {
                    deleteDuplicates(ListNode pointer = 2) {
                        deleteDuplicates(ListNode pointer = 3) {
                            // 只剩一个节点 返回
                        }
                    }
                }
            }
        }
     */

    /**
     * <h3>方法一 递归</h3>
     * 删除排序链表中的所有重复元素，使得每个元素只出现一次
     *
     * @param pointer 链表的指针
     * @return 删除重复元素后的链表头指针
     */
    public ListNode deleteDuplicates1(ListNode pointer) {
        // 如果链表为空或者只有一个元素，则不需要处理，直接返回原链表
        if (pointer == null || pointer.next == null) {
            return pointer;
        }
        // 如果当前节点和下一个节点的值相同，说明需要删除当前节点
        if (pointer.val == pointer.next.val) {
            // 找到第一个与当前节点取值不同的节点
            ListNode x = pointer.next.next;
            while (x != null && x.val == pointer.val) {
                x = x.next;
            }
            // 递归处理要找到的节点及其后续节点
            return deleteDuplicates1(x); // 与pointer取值不同的节点
        } else {
            // 如果当前节点和下一个节点值不同，则保留当前节点
            // 但需要递归出来后续节点，防止后面的节点有重复
            pointer.next = deleteDuplicates1(pointer.next);
            return pointer;
        }
    }

    /*
        p1 p2 p3
        s, 1, 1, 1, 2, 3, null

        p1 p2    p3
        s, 1, 1, 1, 2, 3, null

        p1 p2       p3
        s, 1, 1, 1, 2, 3, null

        p1 p3
        s, 2, 3, null

        p1 p2 p3
        s, 2, 3, null

           p1 p2 p3
        s, 2, 3, null
     */

    /**
     * <h3>方法二</h3>
     * 删除链表中所有的重复元素（连续和非连续的重复元素）
     *
     * @param head 链表的头节点
     * @return 删除重复元素后的链表的头节点
     */
    public ListNode deleteDuplicates2(ListNode head) {
        // 如果链表为空或者只有一个元素，则不需要处理，直接返回原链表
        if (head == null || head.next == null) {
            return head;
        }
        // 创建一个哨兵节点，简化链表操作，避免边界问题
        ListNode sentinel = new ListNode(-1, head);
        // pointer1 用于遍历链表，并作为删除重复节点后的链表的尾节点
        ListNode pointer1 = sentinel;
        // pointer2 和 pointer3 用于查找连续的重复节点
        ListNode pointer2, pointer3;
        // 遍历链表，直到pointer2 和 pointer3 为null
        while ((pointer2 = pointer1.next) != null
                && (pointer3 = pointer2.next) != null) {
            // 如果发现重复节点
            if (pointer2.val == pointer3.val) {
                // 继续向后查找，直到找到最后一个不重复的节点
                while ((pointer3 = pointer3.next) != null
                        && pointer3.val == pointer2.val) {
                }
                // 删除重复节点，将 pointer1 的 next 指向不重复的节点
                // pointer3 找到了不重复的值
                pointer1.next = pointer3;

            } else {
                // 如果当前节点不重复，移动 pointer1，继续检查下一个节点
                pointer1 = pointer1.next;
            }
        }
        // 返回删除重复元素后的链表的头节点
        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 3, 4, 4, 5);
//        ListNode head = ListNode.of(1, 1, 1, 2, 3);
        System.out.println(head);
        System.out.println(new E05Leetcode82().deleteDuplicates2(head));
    }
}
